package LeetCode;

import java.util.ArrayList;
import java.util.LinkedList;

import LeetCode.BinaryTreeInorderTraversal.TreeNode;

public class BTLevelOrderTraversal
{
  // pass both BFS
  public ArrayList<ArrayList<Integer>> levelOrder1(TreeNode root)
  {
    ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
    if (root == null) return results;
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    ArrayList<Integer> line = new ArrayList<Integer>();
    int thislevelcnt = 1;
    int nextlevelcnt = 0;
    while (queue.size() != 0) {
      TreeNode node = queue.pop();
      thislevelcnt--;
      if(node != null){
        line.add(node.val);
        queue.add(node.left);
        queue.add(node.right);
        nextlevelcnt += 2;
      }
      if(thislevelcnt == 0){
        if(!line.isEmpty())
          results.add(line);
        line = new ArrayList<Integer>();
        thislevelcnt = nextlevelcnt;
        nextlevelcnt = 0;
      }
    }
    return results;
  }
  
  

  // pass both DFS
  public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root)
  {
    ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
    if (root == null) return results;
    // Start DFS from the root, level=0
    levelOrderDFS(results, root, 0);
    return results;
  }

  public void levelOrderDFS(ArrayList<ArrayList<Integer>> results,
      TreeNode node, int level)
  {
    // reach a new level, and created this level, add the node
    if (results.size() - 1 < level) {
      ArrayList<Integer> newLevel = new ArrayList<Integer>();
      newLevel.add(node.val);
      results.add(newLevel);
    }
    // append the node to the existing level it correspond to
    else {
      ArrayList<Integer> existLevel = results.get(level);
      existLevel.add(node.val);
      results.set(level, existLevel);
    }
    // DFS recursion on left and right respectively
    if (node.left != null) {
      levelOrderDFS(results, node.left, level + 1);
    }
    if (node.right != null) {
      levelOrderDFS(results, node.right, level + 1);
    }
  }
  
  public void printLevel(TreeNode node, int level, ArrayList<Integer> levelRes){
    if(node == null)
      return;
    if(level == 1){
      levelRes.add(node.val);
    } else {
      printLevel(node.left, level -1, levelRes);
      printLevel(node.right, level -1, levelRes);
    }
  }
  
  public ArrayList<ArrayList<Integer>> printLevelOrder(TreeNode root){
    int height = MaxDepthofBT.maxDepth(root);
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    for(int level = 1; level <= height; level++){
      ArrayList<Integer> levelRes = new ArrayList<Integer>();
      printLevel(root, level, levelRes);
      result.add(levelRes);
    }
    return result;
  }

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    // TODO Auto-generated method stub
    TreeNode root = new TreeNode(3);
    root.left = new TreeNode(9);
    root.right = new TreeNode(20);
    root.right.left = new TreeNode(15);
    root.right.right = new TreeNode(7);
    
    BTLevelOrderTraversal b = new BTLevelOrderTraversal();
    System.out.println(b.printLevelOrder(root));
  }

}
